package listbyorder.access101_200.test106;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/7 10:17
 */
public class Solution1 {

    // 类似于105题
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) return null;
        return helper(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] postorder, int s1, int e1, int[] inorder, int s2, int e2) {
        if (s1 > e1) return null;
        if (s1 == e1) return new TreeNode(postorder[s1]);
        int root_val = postorder[e1];
        TreeNode root = new TreeNode(root_val);
        int in_site = s2;
        for (int i = s2; i <= e2; i++) {
            if (inorder[i] == root_val) {
                in_site = i;
                break;
            }
        }
        int right_len = e2 - in_site;
        root.left = helper(postorder, s1, e1 - right_len - 1, inorder, s2, in_site - 1);
        root.right = helper(postorder, e1 - right_len, e1 - 1, inorder, in_site + 1, e2);
        return root;
    }
}
